package com.leetcode2;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Index2049countHighestScoreNodes {
	
    public static void main(String[] args) throws IOException {
    	String line = "",path = "C:\\Users\\shuoye\\Desktop\\a.txt";
    	BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
    	line = in.readLine();
        int[] parents = stringToIntegerArray(line);
        Index2049countHighestScoreNodes cnt = new Index2049countHighestScoreNodes();
        int ret = cnt.countHighestScoreNodes(parents);
        String out = String.valueOf(ret);
        System.out.println(ret);
    }
    
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
          return new int[0];
        }
        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for(int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }
    
    int cnt = 0;
   	ArrayList<Integer>[] tree;
	long max = 0;
	int n;
	
   	public int countHighestScoreNodes(int[] parents) {
   		n = parents.length;
   		tree = new ArrayList[n];
   		for(int i = 0;i < n;i++) 
   			tree[i] = new ArrayList<>();
   		
   		for (int i = 0; i < parents.length; i++) 
			if(parents[i] != -1) 
				tree[parents[i]].add(i);
   		dfs(0);
   		return cnt;
   	}

   	public int dfs(int node) {
   		int size = n - 1;
   		long ret = 1;
   		
   		for(int index : tree[node]) {
   			int t = dfs(index);
   			size -= t;
   			ret *= t;
   		}
   		
   		if(node != 0) {
   			ret *= size;
   		}
   		
   		if(ret == max) {
   			cnt++;
   		}else if(ret > max) {
   			max = ret;
   			cnt = 1;
   		}
   		return n - size;
   	}
}


